import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Demo1 {
    public List<Integer> findSubstring(String s,String[] words){
        List<Integer> list = new ArrayList<Integer>();
        Map<String,Integer> hash1 = new HashMap<String,Integer>();
        for (String cur:words){
            hash1.put(cur,hash1.getOrDefault(cur,0) + 1);
        }
        Map<String,Integer> hash2 = new HashMap<String,Integer>();
        int len = words[0].length();
        int m = words.length;
        for(int i = 0;i < len;i++){
            hash2.clear();
            for(int left = i,right = i,count = 0;right + len <= s.length();right += len){
                //进窗口
                String in = s.substring(right,right + len);
                hash2.put(in,hash2.getOrDefault(in,0) + 1);
                if (hash2.get(in) <= hash1.getOrDefault(in,0))  count++;
                if (right - left + 1> len*m){
                    //出窗口
                    String out = s.substring(left,left + len);
                    if (hash2.get(out) <= hash1.getOrDefault(out,0)) count--;
                    hash2.put(out,hash2.get(out)-1);
                    left +=len;
                }
                //判断有效count
                if (count == m) list.add(left);
            }
        }
        return list;
    }
}
